import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
//        String[] words = new String[]{"foo","bar"};
//        String s = "barfoothefoobarman";
//        System.out.println(test.findSubstring(s, words).toString());

//        char[] a1 = new char[]{'a', 'b', 'a', 'c', 'd'};
//        char[] a2 = new char[]{'b', 'a', 'b'};
//        Map<Character, Integer> a = new HashMap<>();
//        Map<Character, Integer> b = new HashMap<>();
//        a.put('a', 2);
//        a.put('b', 1);
//        b.put('a', 1);
//        b.put('b', 1);

//         这种方式可以，但是又存在一个问题，还需要判断a是否存在，这里的时间复杂度会非常高！
//         先做出来再说
//        for(char t: b.keySet()) {
//            if(a.containsKey(t) && b.get(t) > a.get(t)) {
//                System.out.println(false);
//            }
//        }
//        System.out.println(true);
        System.out.println(test.minWindow("ADOBECODEBANC", "ABC"));
    }

    public List<Integer> findSubstring(String s, String[] words) {
        /**
         * 串联所有单词的子串
         * */
        // 1 预处理
        // -待处理字符串长度
        int n = s.length();
        // -单位元素长度
        int m = words[0].length();
        int len = words.length;
        // -创建目标字符串map
        Map<String, Integer> target = new HashMap<>();
        for(String str: words) {
            if(target.containsKey(str)) {
                target.put(str, target.get(str) + 1);
            } else {
                target.put(str, 1);
            }
        }
        // -创建返回数组
        List<Integer> retArray = new ArrayList<>();

        // 2 循环滑动
        for(int i = 0; i < m; i++) {
            // -单次滑动（固定窗口）
            int left = i;
            int right = i;
            Map<String, Integer> cur = new HashMap<>();
            // notes: 此处需要取等，因为当right+m == n时，就表明上一次元素right刚好为n-1，合理
            // 这个提示我：当遇到这种写判断条件的情况，一定要充分考虑边界情况，充分考虑！因为比赛时是没有错误案例显示的，到时候就会真的找不到！
            // 我要能够想到，当 right+m == n是什么情况！
            while(right+m <= n) {
                // - 1,进窗口
                String tempStr = s.substring(right, right+m);
                if(cur.containsKey(tempStr)) {
                    cur.put(tempStr, cur.get(tempStr) + 1);
                } else {
                    cur.put(tempStr, 1);
                }

                // - 2,判断
                // notes:此处不使用right - left + 1，是因为right += m，而m是一个单调长度，此时right就是第二个单位的起点了
                if(right - left == m * (len - 1)) {
                    if(target.equals(cur)) {
                        retArray.add(left);
                    }
                    // - 3,出窗口
                    String popStr = s.substring(left, left + m);
                    cur.put(popStr, cur.get(popStr) - 1);
                    if(cur.get(popStr) == 0) {
                        cur.remove(popStr);
                    }
                    left += m;
                }

                right += m;
            }
        }

        // 3 返回值
        return retArray;
    }

    public String minWindow1(String s, String t) {
        /**
         * 最小覆盖子串*/
        // 1 预处理
        int n = s.length();
        char[] chars = s.toCharArray();
        // -返回值
        String retString = "";
        // -目标map
        Map<Character, Integer> target = new HashMap<>();
        for(char x: t.toCharArray()) {
            if(target.containsKey(x)) {
                target.put(x, target.get(x) + 1);
            } else {
                target.put(x, 1);
            }
        }

        // 2 双指针
        int left = 0;
        int right = 0;
        Map<Character, Integer> cur = new HashMap<>();
        int minSize = 0x3f3f3f3f;

        while(right < n) {
            // -1 进窗口
            if(cur.containsKey(chars[right])) {
                cur.put(chars[right], cur.get(chars[right]) + 1);
            } else {
                cur.put(chars[right], 1);
            }
            // -2 判断
            while(demo(target, cur)) {
                // -3 更新（此处更新，进来时必定符合条件）
                if(right - left + 1 < minSize) {
                    minSize = right - left + 1;
                    retString = s.substring(left, right +1);
                }
                // -4 满足时，出窗口至最小
                cur.put(chars[left], cur.get(chars[left]) - 1);
                if(cur.get(chars[left]) == 0) {
                    cur.remove(chars[left]);
                }
                left ++;
            }

            right ++;
        }

        return retString;
    }

    public boolean demo(Map<Character, Integer> target, Map<Character, Integer> cur) {
        /**
         * 根据本题逻辑进行判断*/
        boolean flag = true;
        for(char x: target.keySet()) {
            // -不存在 或者 小于，返回false，表示继续进窗口
            if(!cur.containsKey(x) || cur.containsKey(x) && target.get(x) > cur.get(x)) {
                flag = false;
                break;
            }
        }
        return flag;
    }

    public String minWindow(String s, String t) {
        /**
         * 最小覆盖子串
         * 恐怖的情况出现了，同时存在大写和小写
         * 创建一个更大的即可
         * 因为我们只需存储A-Z和a-z，因此我们选择ASCII最小的‘A’作为减法单位
         * */
        // 1 预处理
        int n = s.length();
        int m = t.length();
        char[] chars = s.toCharArray();
        // -设定单位值（因为可能存在大写和小写）
        char unit = 'A';
        // -返回值
        String retString = "";
        // -目标计数数组
        char[] target = new char[58];
        for(char x: t.toCharArray()) {
            target[x - unit] ++;
        }

        // 2 双指针
        int left = 0;
        int right = 0;
        // -用于计数，当cur中元素个数>=目标中元素时才判断，减少判断次数
        int count = 0;
        char[] cur = new char[58];
        int minSize = 0x3f3f3f3f;

        while(right < n) {
            // -1 进窗口
            cur[chars[right] - unit] ++;
            count ++;

            // -2 判断
            if(count >= m) {
                while(check(target, cur)) {
                    // -3 满足条件，更新
                    if(right - left + 1 < minSize) {
                        minSize = right - left + 1;
                        retString = s.substring(left, right + 1);
                    }

                    // -4 出窗口
                    cur[chars[left] - unit] --;
                    count --;
                    left ++;
                }
            }

            right ++;
        }

        return retString;
    }

    public boolean check(char[] target, char[] current) {
        /**
         * 判断计数数组是否符合条件，若是符合返回true，不符合返回false*/
        for(int i = 0; i < 58; i++) {
            if(current[i] < target[i]) {
                return false;
            }
        }
        return true;
    }
}
